package com.shixianchen.review_the_day_before.day2;

//import com.sun.org.apache.regexp.internal.RE;

/**
 * @author ShiXianChen
 * @version V1.0.0
 * @Description 纸牌游戏  A B 两个玩家玩纸牌，分别在两端拿去纸牌，获取最高的分数
 * @date 2022/10/31 22:10
 */
public class Code05_Cardslnline {

    /**
     * 获取最高玩家的得分数
     * @param arr
     * @return
     */

    public static int getWinnerScore(int[] arr) {

        int n = arr.length+1;
        int[][] dpXian = new int[n][n];
        int[][] dpHou = new int[n][n];

        //将缓存设置成默认值
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dpXian[i][j] = -1;
                dpHou[i][j] = -1;
            }
        }

        //先手函数
        int xian  =  xian(arr,0,arr.length-1,dpXian,dpHou);
        int hou  =  hou(arr,0,arr.length-1,dpXian,dpHou);

        return Math.max(xian,hou);
    }

    private static int xian(int[] arr, int L, int R, int[][] dpXian, int[][] dpHou) {
        //查看缓存中的数据
        if (dpXian[L][R] != -1){
            return dpXian[L][R];
        }

        int ans = 0;
        if (L == R){
            //当只剩一张牌的时候
            ans =  arr[L];
        } else if (L == R -1){
            //当剩余2张牌的时候
            ans =  Math.max(arr[L],arr[R]);
        }else {
            //当拿取L位置的牌
            //获取当前的分数和我作为后手函数最大的值
            int p1 = arr[L] + hou(arr,L+1,R,dpXian,dpHou);

            //拿取R位置的牌
            //获取当前的分数和我作为后手函数最大的值
            int p2 = arr[R] + hou(arr,L,R-1,dpXian,dpHou);

            ans = Math.max(p1,p2);
        }
        //放入缓存
        dpXian[L][R] = ans;
        return ans;
    }

    private static int hou(int[] arr, int L, int R, int[][] dpXian, int[][] dpHou) {
        //是否在缓存中的数据
        if (dpHou[L][R] != -1){
            return dpHou[L][R];
        }
        int ans = 0;
        if (L == R){
            //剩余一整牌
            ans =  arr[L];
        }else if (L == R -1){
            //剩余两张牌的时候
            ans =  Math.max(arr[L],arr[R]);
        }else {
            //剩余多张牌的时候
            // 对手，先手，拿走L位置上牌，你作为先手拿走，L+1....R的牌
            int p1 = xian(arr,L+1,R,dpXian,dpHou);
            //对手，先手，拿走R位置上的牌，你作为先手拿走，L....R的牌
            int p2 = xian(arr,L,R-1,dpXian,dpHou);
            ans = Math.min(p1,p2);
        }

        return ans;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{2,3,48,7,99,1,3,77};
        System.out.println("getWinnerScore(arr) = " + getWinnerScore(arr));
    }

}
